package JZOffer;

import java.util.*;

// 滑动窗口的最大值
public class JzOffer59_I {
    // 分治 + 预处理
    public static int[] maxSlidingWindow(int[] nums, int k) {
        // 前缀
        int[] prefixMax = new int[nums.length];
        // 后缀
        int[] suffixMax = new int[nums.length];

        // 预处理每一组中从前往后的每个数对应组中的最大值
        for (int i = 0; i < nums.length; i++) {
            if (i % k == 0) {
                // 每一组的开始
                prefixMax[i] = nums[i];
            } else {
                // 这个元素是每一组中间的元素, 最大值是这个元素前一个元素预处理最大值的结果与这个元素本身的最大值
                prefixMax[i] = Math.max(prefixMax[i-1], nums[i]);
            }
        }

        // 预处理每一组从后往前的每个数对应组中的最大值
        for (int i = nums.length-1; i >= 0 ; i--) {
            if (i == nums.length-1 || i % k == 0) {
                // 每一组后缀的开始
                suffixMax[i] = nums[i];
            } else {
                // 这个元素是每一组中间的元素, 最大值是这个元素后一个元素预处理最大值的结果与这个元素本身的最大值
                suffixMax[i] = Math.max(suffixMax[i+1], nums[i]);
            }
        }

        // 此时已经预处理完成, 滑动窗口中的最大值 (两种情况) :
        // 1. i 是分组的第一个元素, 代表最大值是这个分组的最后一个元素的预处理结果
        //    也就是 prefixMax(i+k-1) 或者 suffixMax(i) [这两个元素是相等的, 都是一组中的最大值];
        // 2. i 是一个分组中间的元素, 最大值是
        //    (i 所在的分组中由 i 开始到分组末尾的最大值) 和 (i+k-1[窗口末尾]所在的分组中由 i+k-1 到这个分组的开头的最大值) 这两个的最大值
        //    也就是  Math.max(suffixMax(i), prefixMax(i+k-1));
        // 综合以上 2 点, 最大值就是 Math.max(suffixMax(i), prefixMax(i+k-1));
        int[] ans = new int[nums.length-k+1];
        for (int i = 0; i <= nums.length-k; i++) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i+k-1]);
        }
        return ans;
    }


    // 单调队列
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] ans = new int[nums.length-k+1];

        // 先形成窗口
        for (int i = 0; i < k; i++) {
            // 此时不需要考虑窗口左侧元素是此单调队列最大值的情况
            // 但是需要考虑队尾元素是否大于新进入窗口的元素, 如果队尾元素小于新进入窗口的元素, 将队尾元素排出
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.pollLast();
            }
            deque.addLast(nums[i]);
        }
        ans[0] = deque.peekFirst();

        // 窗口已成型
        for (int j = k, i = 1; j < nums.length; j++, i++) {
            // 判断, 此时窗口左边的那个元素是否是当前单调队列中的队首元素, 如果是, 移除队列队首元素
            if (!deque.isEmpty() && deque.peekFirst() == nums[i-1]) {
                deque.pollFirst();
            }
            // 判断, 此时刚刚进入窗口的值是否大于队尾元素的值
            // 如果大于队尾, 循环地将队尾小于新入窗口的值的元素移除
            while (!deque.isEmpty() && nums[j] > deque.peekLast()) {
                deque.pollLast();
            }
            deque.addLast(nums[j]);
            ans[j-k+1] = deque.peekFirst();
        }

        return ans;
    }

    // 优先级队列
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        // 建立一个大根堆, 里面的元素是 num 里的值和它们的下标
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];
            }
        });
        // 最终的结果存放到这个数组里面, 数组的长度根据计算是 原数组的长度-k+1
        int[] ans = new int[nums.length - k + 1];

        // 先将 k 个元素存放进去
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(new int[]{nums[i], i});
        }
        ans[0] = priorityQueue.peek()[0];

        for (int i = k; i < nums.length; i++) {
            priorityQueue.offer(new int[]{nums[i], i});
            // 如果堆顶的元素不在滑动窗口内, 将堆顶的元素删除
            while (priorityQueue.peek()[1] <= i - k) {
                priorityQueue.poll();
            }

            // 这时, 堆顶的元素必定在滑动窗口内了
            ans[i - k + 1] = priorityQueue.peek()[0];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(arr, 3)));
    }
}
